graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a cop-win graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

on which the pursuer (cop) can always win a

pursuit–evasion Pursuit–evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early ...

game against a robber, with the players taking alternating turns in which they can chose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex (one whose closed neighborhood is a subset of another vertex's neighborhood) or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

that constructs a dismantling order. They include the

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

s, and the graphs that contain a

universal vertex In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused ...

Definitions

Pursuit–evasion

Cop-win graphs can be defined by a

game in which two players, a cop and a robber, are positioned at different initial vertices of a given

. The cop chooses an initial vertex first, and then the robber chooses. Next, they play in turns, again with the cop first. On each player's turn, the player may either move to an adjacent vertex or stay put. The game ends, and the cop wins, if the cop can end a turn on the same vertex as the robber. The robber wins by indefinitely evading the cop. A cop-win graph is a graph with the property that, when the players choose starting positions and then move in this way, the cop can always force a win. If an undirected graph is not a cop-win graph, it is called a robber-win graph.

Dismantling

The closed neighborhood of a vertex in a given graph is the set of vertices consisting of itself and all other vertices adjacent to . The vertex is said to be ''dominated'' by another vertex when . That is, and are adjacent, and every other neighbor of is also a neighbor of . call a vertex that is dominated by another vertex an ''irreducible vertex''. A ''dismantling order'' or ''domination elimination ordering'' of a given graph is an ordering of the vertices such that, if the vertices are removed one-by-one in this order, each vertex (except the last) is dominated at the time it is removed. A graph is ''dismantlable'' if and only if it has a dismantling order.

Equivalence of cop-win and dismantlability

Every finite dismantlable graph is cop-win. This can be proved by

mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...

, with a one-vertex graph (trivially won by the cop) as a base case. For a larger graph, let be any dominated vertex. By the induction hypothesis, the cop has a winning strategy on the graph formed by removing , and can follow the same strategy on the original graph by pretending that the robber is on the vertex that dominates whenever the robber is actually on . Following this strategy will result either in an actual win of the game, or in a position where the robber is on and the cop is on the dominating vertex, from which the cop can win in one more move. A cop following this inductive strategy on a graph with vertices takes at most moves to win, regardless of starting position. By choosing the cop's starting position carefully, one can use the same idea to prove that, in an -vertex graph, the cop can force a win in at most moves. Conversely, every cop-win graph has a dominated vertex. For, in a graph with no dominated vertices, if the robber has not already lost, then there is a safe move to a position not adjacent to the cop, and the robber can continue the game indefinitely by playing one of these safe moves at each turn. Additionally, if is a dominated vertex in a cop-win graph, then removing must produce another cop-win graph, for otherwise the robber could play within that subgraph, pretending that the cop is on the vertex that dominates whenever the cop is actually on , and never get caught. It follows by induction from these two principles that every finite cop-win graph is dismantlable.

Closure properties

A family of mathematical objects is said to be closed under a set of operations if combining members of the family always produces another member of that family. In that sense, the family of cop-win graphs is closed under strong products of graphs. Each vertex in the strong product corresponds to a pair of vertices in each of two factor graphs. The cop can win in a strong product of two cop-win graphs by, first, playing to win in one of these two factor graphs, reaching a pair whose first component is the same as the robber. Then, while staying in pairs whose first component is the same as the robber, the cop can play to win in the second of the two factors. For instance, the

king's graph In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m king's graph ...

, a strong product of two

path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...

s, is cop-win. On this graph, the vertices correspond to the squares of a chessboard, and both the cop and robber move like a king in the game of

chess Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to dist ...

, to a square that is adjacent horizontally, vertically, or diagonally. The product-based strategy for the cop would be to first move to the same row as the robber, and then move towards the column of the robber while in each step remaining on the same row as the robber. It is not true that every

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

of a cop-win graph is cop-win. However, certain special induced subgraphs do remain cop-win. define a ''retraction'' of a graph onto one of its induced subgraphs to be a mapping from the vertices of to the vertices of that maps each vertex of to itself, and that maps each pair of adjacent vertices of either to the same vertex as each other or to a pair of adjacent vertices in . Then the family of cop-win graphs is closed under retraction. This is because a cop can win in by simulating a game in . Whenever the winning strategy in would call for the cop to stay put, or to follow an edge whose endpoints are mapped to the same vertex of , the cop stays put in . And in all other cases, the cop follows the edge in that is the image under the retraction of a winning edge in .

Recognition algorithms

Several different strategies are known for checking whether a graph is cop-win, and if so finding a dismantling sequence allowing the cop to win in the graph. These include

s, and a more complicated algorithm based on counting shared neighbors of vertices.

Greedy algorithm

A dismantling order can be found by a simple

that repeatedly finds and removes any dominated vertex. The process succeeds, by reducing the graph to a single vertex, if and only if the graph is cop-win. Therefore, as well as providing an algorithm for finding dismantling orders, this method provides an algorithm for testing whether a given graph is cop-win. One way for this algorithm to find the dominated vertices that it removes is to perform the following steps: *Find all triangles in the graph, and count the number of triangles that each edge participates in. *Repeatedly find a vertex that is an endpoint of an edge participating in a number of triangles equal to the

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...

of minus one, delete , and decrement the triangles per edge of each remaining edge that formed a triangle with . In a graph with vertices, edges, and degeneracy , this process can be carried out in time .

Counting neighbors

An alternative and more complicated algorithm by involves maintaining a number called the ''deficit'' for each adjacent pair of vertices , which counts the number of neighbors of that are not neighbors of . If this number becomes zero, after other vertices have been removed, then is dominated by and may also be removed. It constructs and maintains the actual ''deficit set'' (neighbors of that are not neighbors of ) only for pairs for which the deficit is small. To speed up its computations, Spinrad's algorithm uses a subroutine for counting neighbors among small blocks of vertices. If is a set of vertices that the algorithm has selected to be a block, then for any other vertex, the set of neighbors of that vertex in can be represented as a binary number with bits. These numbers allow the algorithm to count, for any two vertices and , how much contributes to the deficit of and , in constant time, by a combination of bitwise operations and table lookups. Using this subroutine, the algorithm performs the following steps: *Create blocks from an arbitrary partition of the vertices, and find the numbers representing the neighbors of each vertex in each block. *Use the block-counting subroutine to compute the deficit for all adjacent pairs of vertices. *Repeat the following steps until all vertices have been removed: **Construct the deficit set for all adjacent pairs that have deficit at most and that have not already had this set constructed. The initial system of blocks can be used to speed up this construction. **Repeat the following steps times: ***Find a pair with constructed but empty deficit set. If no such pair exists, the graph is not cop-win; in this case, abort the algorithm. ***Delete vertex ***Remove from all constructed deficit sets that it belongs to. **Construct a block of the removed vertices and numbers representing all other vertices' adjacencies within this block. **Use the block-counting subroutine, on this one block, to update the deficits for all edges. Spinrad states the total time for this algorithm as .

In infinite graphs

The

computability Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is clo ...

of algorithmic problems involving cop-win graphs has also been studied for

infinite graph This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

s. In the case of infinite graphs, it is possible to construct computable countably infinite graphs, on which an omniscient robber could always evade any cop, but for which no algorithm can follow this strategy. These graphs can even be infinite trees, with a finite number of edges per vertex. By

Kőnig's lemma Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computab ...

, such a tree must have an infinite path, and an omniscient robber can win by walking away from the cop along this path, but the path cannot be found by an algorithm. Instead, every algorithm for choosing moves for the robber can be beaten by a cop who simply walks in the tree along the unique path towards the robber. Analogously, it is possible to construct computable countably infinite cop-win graphs, on which an omniscient cop has a winning strategy that always terminates in a finite number of moves, but for which no algorithm can follow this strategy. On such graphs, every algorithm for choosing moves for the cop can be evaded indefinitely by the robber.

Related families of graphs

Every finite

is a dismantlable graph, and every elimination ordering of a chordal graph (an ordering of the vertices in which the later neighbors of each vertex form a

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

) is a valid dismantling order. However, there exist infinite chordal graphs, and even infinite chordal graphs of

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

two, that are not cop-win. For other types of graphs, there may exist infinite cop-win graphs of that type even when there are no finite ones; for instance, this is true for the

vertex-transitive graph In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive ...

s that are not

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

s. A

in a graph is a vertex that is adjacent to all other vertices. Whenever a graph has a

, it is dismantlable, because every other vertex is dominated by the universal vertex, and any vertex ordering that places the universal vertex last is a valid dismantling order. Conversely, almost all dismantlable graphs have a universal vertex, in the sense that, among all -vertex dismantlable graphs, the fraction of these graphs that have a universal vertex goes to one in the limit as goes to infinity. The

visibility graph In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge rep ...

s of

simple polygon In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If ...

s are always cop-win. These are graphs defined from the vertices of a polygon, with an edge whenever two vertices can be connected by a line segment that does not pass outside the polygon. (In particular, vertices that are adjacent in the polygon are also adjacent in the graph.) Even when the cop and robber are allowed to move on straight line segments within the polygon, rather than vertex-to-vertex, the cop can win by always moving on the first step of a shortest path to the robber. Such a move cuts off part of the polygon which the robber can never double back to reach. When the cop starts at a vertex and the robber is restricted to moves between vertices, this strategy also limits the cop to vertices, so it is a valid winning strategy for the visibility graph. 4-cube t3 B2

The hereditarily cop-win graphs are the graphs in which every isometric subgraph is cop-win. This is not true for all cop-win graphs; for instance, the five-vertex

wheel graph A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...

is cop-win but contains an isometric 4-cycle, which is not cop-win, so this wheel graph is not hereditarily cop-win. The hereditarily cop-win graphs are the same as the bridged graphs, graphs in which every cycle of length four or more has a shortcut, a pair of vertices closer in the graph than they are in the cycle. A cop-win graph is hereditarily cop-win if and only if it has neither the 4-cycle nor 5-cycle as

induced cycle In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...

s. For a hereditarily cop-win graph, the reversal of any breadth-first traversal is a valid dismantling order, from which it follows that any vertex can be chosen as the last vertex of a dismantling order. A similar game with larger numbers of cops can be used to define the

cop number In graph theory, a branch of mathematics, the cop number or copnumber of an undirected graph is the minimum number of cops that suffices to ensure a win (i.e., a capture of the robber) in a certain pursuit–evasion game on the graph. Rules In th ...

of a graph, the smallest number of cops needed to win the game. The cop-win graphs are exactly the graphs of cop number equal to one. Bonato and Nowakowski describe this game intuitively as the number of ghosts that would be needed to force a Pac-Man player to lose, using the given graph as the field of play. The game used to define cop number should be distinguished from a different cops-and-robbers game used in one definition of

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

, which allows the cops to move to arbitrary vertices rather than requiring them to travel along graph edges.

History

The game with a single cop, and the cop-win graphs defined from it, were introduced by . Another early reference is the work of , who were introduced to the game by G. Gabor. The game with multiple cops, and the cop number defined from it, were first studied by .

References

{{reflist, refs= {{citation , last1 = Aigner , first1 = M. , last2 = Fromme , first2 = M. , issue = 1 , journal = Discrete Applied Mathematics , mr = 739593 , pages = 1–11 , title = A game of cops and robbers , doi = 10.1016/0166-218X(84)90073-8 , volume = 8 , year = 1984, doi-access = free {{citation , last1 = Anstee , first1 = R. P. , last2 = Farber , first2 = M. , doi = 10.1016/0095-8956(88)90093-7 , issue = 1 , journal = Journal of Combinatorial Theory , mr = 923263 , pages = 22–28 , series = Series B , title = On bridged graphs and cop-win graphs , volume = 44 , year = 1988, doi-access = free {{citation , last1 = Bonato , first1 = A. , last2 = Golovach , first2 = P. , last3 = Hahn , first3 = G. , last4 = Kratochvíl , first4 = J. , author4-link = Jan Kratochvíl , doi = 10.1016/j.disc.2008.04.004 , issue = 18 , journal = Discrete Mathematics , mr = 2567962 , pages = 5588–5595 , title = The capture time of a graph , volume = 309 , year = 2009, doi-access = free {{citation , last1 = Bonato , first1 = Anthony , last2 = Kemkes , first2 = Graeme , last3 = Prałat , first3 = Paweł , doi = 10.1016/j.disc.2012.02.018 , doi-access = free , issue = 10 , journal = Discrete Mathematics , mr = 2901161 , pages = 1652–1657 , title = Almost all cop-win graphs contain a universal vertex , volume = 312 , year = 2012 For the fact that a strong product of paths is cop-win, see {{harvtxt, Nowakowski, Winkler, 1983. For the fact that the king's graph is a strong product of paths, see {{citation , last1 = Berend , first1 = Daniel , last2 = Korach , first2 = Ephraim , last3 = Zucker , first3 = Shira , contribution = Two-anticoloring of planar and related graphs , contribution-url = http://www.emis.de/journals/DMTCS/pdfpapers/dmAD0130.pdf , location = Nancy , mr = 2193130 , pages = 335–341 , publisher = Association for Discrete Mathematics & Theoretical Computer Science , series = Discrete Mathematics & Theoretical Computer Science Proceedings , title = 2005 International Conference on Analysis of Algorithms , year = 2005 {{citation , last1 = Bonato , first1 = Anthony , last2 = Nowakowski , first2 = Richard J. , doi = 10.1090/stml/061 , isbn = 978-0-8218-5347-4 , mr = 2830217 , publisher = American Mathematical Society , location = Providence, RI , series = Student Mathematical Library , title = The Game of Cops and Robbers on Graphs , volume = 61 , year = 2011 {{citation , last = Chepoi , first = Victor , doi = 10.1137/S0895480195291230 , issue = 3 , journal =

SIAM Journal on Discrete Mathematics '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was estab ...

, mr = 1628110 , pages = 414–436 , title = On distance-preserving and domination elimination orderings , volume = 11 , year = 1998 {{citation , last = Chepoi , first = Victor , doi = 10.1006/jctb.1996.1726 , issue = 1 , journal = Journal of Combinatorial Theory , mr = 1426753 , pages = 97–100 , series = Series B , title = Bridged graphs are cop-win graphs: an algorithmic proof , volume = 69 , year = 1997, doi-access = free {{citation , last = Gavenčiak , first = Tomáš , doi = 10.1016/j.disc.2010.01.015 , issue = 10–11 , journal = Discrete Mathematics , mr = 2601265 , pages = 1557–1563 , title = Cop-win graphs with maximum capture-time , volume = 310 , year = 2010, doi-access = free {{citation , last1 = Hahn , first1 = Geňa , last2 = Laviolette , first2 = François , last3 = Sauer , first3 = Norbert , last4 = Woodrow , first4 = Robert E. , doi = 10.1016/S0012-365X(02)00260-1 , issue = 1–3 , journal = Discrete Mathematics , mr = 2002070 , pages = 27–41 , title = On cop-win graphs , volume = 258 , year = 2002, doi-access = free {{citation , last1 = Lin , first1 = Min Chih , last2 = Soulignac , first2 = Francisco J. , last3 = Szwarcfiter , first3 = Jayme L. , arxiv = 1005.2211 , doi = 10.1016/j.tcs.2011.12.006 , journal =

Theoretical Computer Science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

, mr = 2891574 , pages = 75–90 , title = Arboricity, {{mvar, h-index, and dynamic algorithms , volume = 426–427 , year = 2012 , s2cid = 15827218 {{citation , last1 = Lubiw , first1 = Anna , author1-link = Anna Lubiw , last2 = Snoeyink , first2 = Jack , last3 = Vosoughpour , first3 = Hamideh , arxiv = 1601.01298 , doi = 10.1016/j.comgeo.2017.07.001 , journal = Computational Geometry , mr = 3693353 , pages = 14–27 , title = Visibility graphs, dismantlability, and the cops and robbers game , volume = 66 , year = 2017 {{citation , last1 = Nowakowski , first1 = Richard , last2 = Winkler , first2 = Peter , author2-link = Peter Winkler , doi = 10.1016/0012-365X(83)90160-7 , issue = 2–3 , journal = Discrete Mathematics , mr = 685631 , pages = 235–239 , title = Vertex-to-vertex pursuit in a graph , volume = 43 , year = 1983, doi-access = free {{citation , last = Quilliot , first = Alain , language = fr , pages = 131–145 , publisher = Pierre and Marie Curie University , series = Thèse de 3ème cycle , title = Jeux et pointes fixes sur les graphes , trans-title = Games and fixed points on graphs , year = 1978, as cited by {{harvtxt, Bonato, Nowakowski, 2011 {{citation , last = Spinrad , first = Jeremy P. , doi = 10.1016/S0166-218X(03)00295-6 , issue = 1–2 , journal = Discrete Applied Mathematics , mr = 2057611 , pages = 203–213 , title = Recognizing quasi-triangulated graphs , volume = 138 , year = 2004, doi-access = free {{citation , last1 = Seymour , first1 = Paul D. , author1-link = Paul Seymour (mathematician) , last2 = Thomas , first2 = Robin , author2-link = Robin Thomas (mathematician) , doi = 10.1006/jctb.1993.1027 , doi-access = free , issue = 1 , journal =

Journal of Combinatorial Theory, Series B The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, pages = 22–33 , title = Graph searching and a min-max theorem for tree-width , volume = 58 , year = 1993 {{citation , last = Stahl , first = Rachel D. , date = September 2021 , doi = 10.1007/s00153-021-00794-3 , journal =

Archive for Mathematical Logic '' Archive for Mathematical Logic'' is a peer review, peer-reviewed mathematics journal published by Springer Science+Business Media. It was established in 1950 and publishes articles on mathematical logic. Abstracting and indexing The journal is ...

, title = Computability and the game of cops and robbers on graphs, volume = 61 , issue = 3–4 , pages = 373–397 , s2cid = 244214571

External links

Dismantlable graphs
Information System on Graph Classes and their Inclusions Graph families Pursuit–evasion